package 刷题.leedcode106;

public class Solution{
    int index =0;
    public TreeNode buildTree(int[] inorder,int[] postorder) {
        /**
         * 中序：左中右
         * 后序：左右中
         * 则后序遍历的数组的最后一个元素是根节点
         * 在中序遍历中找到根节点下标，左边为左子树，右边为右子树
         * 根据这种方法递归
         */
        //index中后序遍历中找根节点，然后将中序遍历分成左右两部分
        index = postorder.length - 1;
        return buildTree(inorder,postorder,0,inorder.length);
    }
    private TreeNode buildTree(int[] inorder,int[] postorder,int left,int right){
//        int left = 0;
//        int right = inorder.length;
        //left表示中序遍历开始位置
        //right表示中序遍历长度
        if(left == right){//长度为0，空树
            return null;
        }
        //创建一个根节点,后序遍历的最后一个是根节点，依次递归往前
        TreeNode root = new TreeNode(postorder[index]);
        //然后在中序遍历中找到根的位置
        int rootIdx = left;
        while(rootIdx < right){
            if (inorder[rootIdx] == postorder[index]){
                break;//找到中序遍历中的根节点
            }
            rootIdx++;//中序遍历往前走一下
        }
        //上面通过while循环找到了根节点，接下来后序遍历往前走一个位置，为右子树的根节点
        index--;
        //通过递归，找到各个结点
        //这里要注意一个问题，左子树的right和右子树的left
        //左子树的right在中序遍历得根节点的前一个位置结束
        //右子树left是中序遍历的根节点的后一个位置开始
        //左闭右开区间
        //创建右子树
        root.right = buildTree(inorder,postorder,rootIdx + 1,right);
        //创建左子树
        root.left = buildTree(inorder,postorder,left,rootIdx);
        return root;
    }
}
